package common

import (
	"fmt"
	"strconv"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func (n *TreeNode) Show() {
	if n == nil {
		fmt.Print("null->")
		return
	}
	fmt.Printf("%d->", n.Val)
}

func (t *TreeNode) prefixWalk() {
	if t == nil {
		fmt.Print("null->")
		return
	}
	t.Show()
	t.Left.prefixWalk()
	t.Right.prefixWalk()
}

func PrefixWalk(root *TreeNode) {
	root.prefixWalk()
	fmt.Println()
}

func (t *TreeNode) midWalk() {
	if t == nil {
		fmt.Print("null->")
		return
	}
	t.Left.midWalk()
	t.Show()
	t.Right.midWalk()
}

func MidWalk(root *TreeNode) {
	root.midWalk()
	fmt.Println()
}

func (t *TreeNode) suffixWalk() {
	if t == nil {
		fmt.Print("null->")
		return
	}
	t.Left.suffixWalk()
	t.Right.suffixWalk()
	t.Show()
}

func SuffixWalk(root *TreeNode) {
	root.suffixWalk()
	fmt.Println()
}

// 前缀遍历转换成数组，转换后，先记录根，然后左子树，右子树
func SerializeDFS(root *TreeNode, res *[]string) {
	if root == nil {
		*res = append(*res, "null")
		return
	}
	*res = append(*res, fmt.Sprintf("%d", root.Val))
	SerializeDFS(root.Left, res)
	SerializeDFS(root.Right, res)
}

// 反序列化，注意idx传入指针
func DeSerialize(arr []string, idx *int) (root *TreeNode) {
	if arr[(*idx)] == "null" {
		(*idx) += 1 // 注意null情况下也要继续+1
		return
	}
	v, _ := strconv.ParseInt(arr[(*idx)], 10, 64)
	root = &TreeNode{Val: int(v)}
	(*idx) += 1
	root.Left = DeSerialize(arr, idx)  // 先反序列化左子树
	root.Right = DeSerialize(arr, idx) // 再反序列化右子树
	return
}

// BFS 序列化的结果是层序遍历，左右节点相邻
func SerializeBFS(root *TreeNode) (res []string) {
	var queue []*TreeNode
	queue = append(queue, root)
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			head := queue[0]
			queue = queue[1:]
			if head == nil {
				res = append(res, "null")
				continue
			}
			res = append(res, fmt.Sprintf("%d", head.Val))
			queue = append(queue, head.Left)
			queue = append(queue, head.Right)
		}
	}
	return
}

func DeSerializeBFS(arr []string) (root *TreeNode) {
	var queue []*TreeNode
	if arr[0] == "null" {
		return
	}
	v, _ := strconv.ParseInt(arr[0], 10, 64)
	root = &TreeNode{Val: int(v)}
	queue = append(queue, root)
	// 从当前位置0开始遍历，i+1就是bfs的左节点，i+2是bfs的右节点
	for i := 0; i < len(arr); {
		if len(queue) == 0 {
			break
		}
		head := queue[0]
		queue = queue[1:]
		// 左节点
		if i+1 < len(arr) {
			i++
			if arr[i] != "null" {
				v, _ := strconv.ParseInt(arr[i], 10, 64)
				leftNode := &TreeNode{Val: int(v)}
				head.Left = leftNode
				queue = append(queue, leftNode)
			}
		}
		// 右节点
		if i+1 < len(arr) {
			i++
			if arr[i] != "null" {
				v, _ := strconv.ParseInt(arr[i], 10, 64)
				rightNode := &TreeNode{Val: int(v)}
				head.Right = rightNode
				queue = append(queue, rightNode)
			}
		}
	}
	return
}
